验证回文字符串(二)

[编程题]验证回文字符串(二)

热度指数：1492 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串，请问最多删除一个的情况下，能否组成一个回文字符串。

回文字符串：正着读和反着读是一样的字符串。

数据范围：字符串长度满足 $1 \le n \le 10^5 \$ ，字符串中仅包含小写英文字母

示例1

输入

"nowwon"

输出

true

示例2

输入

"nowewon"

输出

true

示例3

输入

"noweawon"

输出

true

示例4

输入

"noowwwn"

输出

false

算法知识视频讲解

JavaScript Node

几号发货

提供一个删除k个字符思路

function palindrome(str) {
    function dfs(s, i, j, k) {
        if (k < 0) return false;
        if (j - i <= 1) return true;
        while (i < j) {
            if (s[i] == s[j]) {
                i++;
                j--;
            } else {
                return (
                    dfs(s, i + 1, j, k - 1) ||
                    dfs(s, i, j - 1, k - 1) ||
                    dfs(s, i + 1, j - 1, k - 2)
                );
            }
        }
        return true;
    }
    return dfs(str,0,str.length-1,1)
}

发表于 2022-11-17 12:09:06 回复(0)